package util;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Egor Kulikov (kulikov@devexperts.com)
 */
class CollectionUtil {
	public static class MultiSet<K> {
		private Map<K, Integer> map = new HashMap<K, Integer>();
		private int size = 0;

		public int size() {
			return size;
		}

		public int entryCount() {
			return map.size();
		}

		public boolean isEmpty() {
			return size == 0;
		}

		public boolean contains(K key) {
			return map.containsKey(key);
		}

		public int add(K key) {
			Integer value = map.get(key);
			if (value == null)
				value = 0;
			value++;
			size++;
			map.put(key, value);
			return value;
		}

		public int remove(K key) {
			Integer value = map.get(key);
			if (value == null)
				return 0;
			value--;
			size--;
			if (value == 0)
				map.remove(key);
			else
				map.put(key, value);
			return value + 1;			
		}

		public int removeAll(K key) {
			int value = map.remove(key);
			size -= value;
			return value;
		}

		public int get(K key) {
			Integer value = map.get(key);
			if (value == null)
				value = 0;
			return value;
		}

		public void clear() {
			map.clear();
			size = 0;
		}

		@Override
		public boolean equals(Object o) {
			if (this == o)
				return true;
			if (o == null || getClass() != o.getClass())
				return false;

			MultiSet multiSet = (MultiSet) o;

			return !(map != null ? !map.equals(multiSet.map) : multiSet.map != null);

		}

		@Override
		public int hashCode() {
			return map.hashCode();
		}
	}

	public static class MaximumIntervalTree {
		private int[] left;
		private int[] right;
		private int[] value;

		public MaximumIntervalTree(int size) {
			left = new int[4 * size];
			right = new int[4 * size];
			value = new int[4 * size];
			init(0, size, 0);
		}

		private void init(int left, int right, int root) {
			this.left[root] = left;
			this.right[root] = right;
			if (right - left > 1) {
				init(left, (left + right) / 2, 2 * root + 1);
				init((left + right) / 2, right, 2 * root + 2);
			}
		}

		public int getValue(int left, int right) {
			return getValue(left, right, 0);
		}

		private int getValue(int left, int right, int root) {
			if (left >= this.right[root] || right <= this.left[root])
				return 0;
			if (left <= this.left[root] && right >= this.right[root])
				return value[root];
			return Math.max(getValue(left, right, 2 * root + 1), getValue(left, right, 2 * root + 2));
		}

		public void putValue(int position, int value) {
			putValue(position, value, 0);
		}

		private void putValue(int position, int value, int root) {
			if (left[root] > position || right[root] <= position)
				return;
			this.value[root] = Math.max(this.value[root], value);
			if (right[root] - left[root] > 1) {
				putValue(position, value, 2 * root + 1);
				putValue(position, value, 2 * root + 2);
			}
		}
	}

	public static class SumIntervalTree {
		private int[] left;
		private int[] right;
		private int[] value;

		public SumIntervalTree(int size) {
			left = new int[4 * size];
			right = new int[4 * size];
			value = new int[4 * size];
			init(0, size, 0);
		}

		private void init(int left, int right, int root) {
			this.left[root] = left;
			this.right[root] = right;
			if (right - left > 1) {
				init(left, (left + right) / 2, 2 * root + 1);
				init((left + right) / 2, right, 2 * root + 2);
			}
		}

		public int getValue(int position) {
			return getValue(position, 0);
		}

		private int getValue(int position, int root) {
			if (position >= this.right[root] || position < this.left[root])
				return 0;
			if (this.right[root] - this.left[root] == 1)
				return value[root];
			return value[root] + getValue(position, 2 * root + 1) + getValue(position, 2 * root + 2);
		}

		public void putValue(int left, int right, int value) {
			putValue(left, right, value, 0);
		}

		private void putValue(int left, int right, int value, int root) {
			if (this.left[root] >= right || this.right[root] <= left)
				return;
			if (this.left[root] >= left && this.right[root] <= right) {
				this.value[root] += value;
				return;
			}
			putValue(left, right, value, 2 * root + 1);
			putValue(left, right, value, 2 * root + 2);
		}
	}
}
